/********************************************************************
 * Name: Stephen Durfey
 * Class: cs335
 * Prof: Dr. Michael Poor
 * Description: This simple program uses recursion in 3 of the 4 print 
 * functions of a binary search tree implementation. 
 ********************************************************************/

#include <queue>
#include <iostream>
#include <cstdlib>
using namespace std;
struct BSTNode {
		int value;
		BSTNode* left;
		BSTNode* right;
};

void unbalancedInsert(BSTNode* &head, int v)
{

//empty tree or foundlocation
if(head == NULL)
{
	head = new BSTNode;
	head->value = v;
	head->left = NULL;
	head->right = NULL;

}
else if(v < head->value)
{
	unbalancedInsert(head->left, v);
}

else if(v > head->value)
{
	unbalancedInsert(head->right, v);
}

else 
{
	cout << "Duplicate ignored" << endl;
}

}
//traverses the binary tree in order, first printing out the left node
//then the root node, and finally the right node.
void inOrder(BSTNode* root)
{
    if(root != NULL)
    {
        inOrder(root->left);
        cout << root->value << " ";
        inOrder(root->right);
    }
}
//traverses the tree in post-order. first prints out the left node, then the
//right node, and finally the root node.
void postOrder(BSTNode* root)
{
    if(root != NULL)
    {
        postOrder(root->left);
        postOrder(root->right);
        cout << root->value << " ";
    }
	
}

//traverses the tree in preOrder conditions. first prints out the root node,
//followed by the left node, and then the right node.
void preOrder(BSTNode* root)
{
    if(root != NULL)
    {
        cout << root->value << " ";
        preOrder(root->left);
        preOrder(root->right);
    }
	
}

//performs a breadth first traversal of the tree. first pushes the root node
//onto the queue, checks to see if the node has children, and pushes them on
//in order from left to right if they exist. prints out the tree level by level
//until the queue is empty.
void levelOrder(BSTNode* root)
{
    queue<BSTNode> BSTHolder;
    BSTNode placeHolder;
    
    if(root != NULL)
    {
        BSTHolder.push(*(root));
        
        while(!BSTHolder.empty())
        {
            placeHolder = BSTHolder.front();
            if(placeHolder.left != NULL)
            {
                BSTHolder.push(*(placeHolder.left));
            }
            if(placeHolder.right != NULL)
            {
                BSTHolder.push(*(placeHolder.right));
            }
            cout << placeHolder.value << " ";
            BSTHolder.pop();
        }
    }
}


int main() {
	
	//create the tree
	BSTNode* head = NULL;
	unbalancedInsert(head, 54);
	unbalancedInsert(head, 22);
	unbalancedInsert(head, 17);
	unbalancedInsert(head, 41);
	unbalancedInsert(head, 36);
	unbalancedInsert(head, 30);
	unbalancedInsert(head, 74);
	unbalancedInsert(head, 76);
	unbalancedInsert(head, 26);
	unbalancedInsert(head, 27);
	unbalancedInsert(head, 45);
	unbalancedInsert(head, 82);
	
	cout << endl;
	cout << "Ricky to the rescue:" << endl;
	cout << "printing inorder: ";
	inOrder(head);
	cout << endl;
	cout<< "Answer:           17 22 26 27 30 36 41 45 54 74 76 82";
	cout << endl;
	cout << endl;
	cout << "printing postorder: ";
	postOrder(head);
	cout << endl;
	cout <<"Answer:             17 27 26 30 36 45 41 22 82 76 74 54  ";
	cout << endl;
	
	cout << endl;
	cout << endl;
	cout << "Stacey saves the day" << endl;
	cout << "printing preorder: ";
	preOrder(head);
cout << endl;
	cout <<"Answer:            54 22 17 41 36 30 26 27 45 74 76 82";
	cout << endl;
	cout << endl;
	cout << "Quiet down, Quinn's in Town" << endl;
	cout << "printing levelorder: ";
	levelOrder(head);
	cout << endl;

	cout <<"Answer:              54 22 74 17 41 76 36 45 82 30 26 27";
	cout << endl;
	
	
	return 0;
}
